class Solution(object):
    def connect(self, root):
        """
        :type root: Node
        :rtype: Node
        """
        if root == None:
            return root

        queue = collections.deque()
        queue.append(root)

        while len(queue) > 0:
            size = len(queue)
            for i in range(size):
                node = queue.popleft()
                #非最后一个节点
                if len(queue) > 0 and i != size - 1:
                    node.next = queue[0]

                if node.left is not None:
                    queue.append(node.left)
                if node.right is not None:
                    queue.append(node.right)
        return root
